//class Solution
//{
//	bool vis[21][21];
//	int dx[4] = { 1, -1, 0, 0 };
//	int dy[4] = { 0, 0, 1, -1 };
//	int ret;
//	int m, n, step;
//public:
//	int uniquePathsIII(vector<vector<int>>& grid)
//	{
//		m = grid.size(), n = grid[0].size();
//		int bx = 0, by = 0;
//		for (int i = 0; i < m; i++)
//			for (int j = 0; j < n; j++)
//				if (grid[i][j] == 0) step++;
//				else if (grid[i][j] == 1)
//				{
//					bx = i;
//					by = j;
//				}
//		step += 2;
//		vis[bx][by] = true;
//		dfs(grid, bx, by, 1);
//		return ret;
//	}
//	void dfs(vector<vector<int>>& grid, int i, int j, int count)
//	{
//		if (grid[i][j] == 2)
//		{
//			if (count == step) 
//				ret++;
//			return;
//		}
//		for (int k = 0; k < 4; k++)
//		{
//			int x = i + dx[k], y = j + dy[k];
//			if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]
//				!= -1)
//			{
//				vis[x][y] = true;
//				dfs(grid, x, y, count + 1);
//				vis[x][y] = false;
//			}
//		}
//	}
//};



//class Solution
//{
//	int dx[4] = { 0, 0, 1, -1 };
//	int dy[4] = { 1, -1, 0, 0 };
//	int m, n;
//	int prev;
//public:
//	vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
//		int color)
//	{
//		if (image[sr][sc] == color) return image;
//		m = image.size(), n = image[0].size();
//		prev = image[sr][sc];
//		dfs(image, sr, sc, color);
//		return image;
//	}
//	void dfs(vector<vector<int>>& image, int i, int j, int color)
//	{
//		image[i][j] = color;
//		for (int k = 0; k < 4; k++)
//		{
//			int x = i + dx[k], y = j + dy[k];
//			if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
//			{
//				dfs(image, x, y, color);
//			}
//		}
//	}
//};





class Solution
{
	int tmp[50010];
public:
	int reversePairs(vector<int>& nums)
	{
		return mergeSort(nums, 0, nums.size() - 1);
	}
	int mergeSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return 0;
		int ret = 0;
		int mid = (left + right) >> 1;
		ret += mergeSort(nums, left, mid);
		ret += mergeSort(nums, mid + 1, right);
		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right) 
		{
			if (nums[cur1] <= nums[cur2])
			{
				tmp[i++] = nums[cur1++];
			}
			else
			{
				ret += mid - cur1 + 1;
				tmp[i++] = nums[cur2++];
			}
		}
		while (cur1 <= mid) tmp[i++] = nums[cur1++];
		while (cur2 <= right) tmp[i++] = nums[cur2++];
		for (int j = left; j <= right; j++)
			nums[j] = tmp[j - left];

		return ret;
	}
};